1. Technical Field
This invention generally relates to computer systems. More specifically, this invention relates to a method and apparatus for reordering the packaging of procedures within a computer program.
2. Background Art
The development of the EDVAC computer system in 1948 is generally considered the beginning of the computer era. Since that time, dramatic advances in both hardware and software (e.g., computer programs) have drastically improved the performance of computer systems. Modern software has become very complex when compared to early computer programs. Many modern computer programs have tens or hundreds of thousands of instructions. The execution time (and hence, performance) of a computer program is very closely related to the number of instructions that are executed as the computer program runs. Thus, as the size and complexity of computer programs increase, the execution time of the computer program increases as well.
Unlike early computer programs, modern computer programs are typically written in a high-level language that is easy to understand by a human programmer. Special software tools known as compilers and linkers take the human-readable form of a computer program, known as "source code", and convert it into "machine code" or "object code" instructions that may be executed by a computer system. Because a compiler and its associated linker generate the stream of machine code instructions that are eventually executed on a computer system, the manner in which the compiler and linker package procedures within the computer program affects the performance of the computer program.
In particular, the ordering of procedures within a computer program affects the performance of the memory paging system in a computer system. Nearly all computer systems have auxiliary storage, such as a hard disk drive, that has large storage capacity, and is relatively inexpensive yet slow compared to main memory. Main memory is typically comprised of Random Access Memory (RAM), which has a much smaller storage capacity and is more expensive than primary storage, yet it is very fast. Instructions and data are typically moved between primary storage and main memory in "pages." A "page" consists of a predefined number of bytes (typically a power of two), and is the fundamental unit of transfer between primary storage and main memory. A predetermined number of pages are typically set aside in main memory for storing pages as they are moved between auxiliary storage and main memory. When a processor within a computer system begins executing a computer program, the memory paging system fills the portion of main memory allocated to paging with pages from primary storage. When the processor needs data that is not in any of the pages in main memory, the memory paging system selects one or more pages that are replaced by new pages from primary storage. Swapping pages in and out of memory requires time and system resources, and therefore degrades system performance. In other words, the fewer the number of page swaps, the better.
In order to optimize the performance of modern computer programs, profilers have been developed to predict and/or measure the run-time behavior of a computer program. Profilers typically generate profile data that estimates how often different portions of the computer program are executed. Using profile data, a compiler, a linker, or a separate optimizer program may make decisions regarding the preferred order of procedures within the computer program in order to improve the performance of the computer system.
Known prior art systems generate profile data that is used by a linker to determine the order of all procedures within a computer program. For many sophisticated computer programs, such as operating systems, the size of the computer program is quite large, consisting of numerous modules. A module is a subset of a computer program that may be independently compiled (i.e., compiled separately from the rest of the modules). A module generally has one or more procedures. While reordering all of the procedures in a computer program may produce a near-optimal arrangement of procedures, it has a negative effect on the maintainability of the computer program. For example, when a problem or "bug" is discovered in the computer program, the bug needs to be fixed with a minimum of disruption to the rest of the computer program. Likewise, when an enhancement is made to the computer program, there needs to be a way to easily add the enhancement. Ideally, a small portion of the computer program (e.g., one or more modules) may be changed to fix the bug or to add the enhancement. However, replacing one or two modules may be problematic if the procedures within the replaced module have been packaged among procedures in many other modules.
If the procedures in a computer program have been interspersed across module boundaries, the most common way to assure the correct operation of the computer program is to supply an entire new program when a bug is fixed or an enhancement is made. However, in the case of large programs like operating systems, the prospect of sending out the entire program each time a bug fix is needed (or an enhancement is made) is prohibitively expensive. In addition, for some computer programs (again, like operating systems), the program needs to continue running while the updated modules are added. Shipping the entire program would require the computer system to be shut down while the new computer program is loaded, an untenable solution in many circumstances. Faced with these issues and with prior art solutions, there exist two primary options: 1) allow global procedure reordering, which makes maintenance difficult but enhances the performance of the code; or 2) forego the advantages of global procedure reordering so that procedures stay in the modules where they are created, making maintenance easier at the cost of slower execution time for the code. Without improved apparatus and methods for the reordering of procedures in a computer program based on profile data in a way that allows maintainability of the computer program, the computer industry will continue to suffer from this undesirable tradeoff.